Computer generated images are typically made up of many differing components or graphical elements which are rendered and composited together to create a final image. In recent times, an “alpha channel” (also known as a “matte”, an “opacity channel”, or simply “opacity”) has been commonly used in generating images. The alpha channel contains information regarding the transparent nature of each element. The alpha channel is stored alongside each instance of a colour, so that, for example, a pixel-based image with opacity stores an alpha (or opacity) value as part of the representation of each pixel. An element without explicit alpha channel information is typically understood to be fully opaque within some defined bounds of the element, and assumed to be completely transparent outside those bounds.
An expression tree offers a systematic means for representing an image in terms of its constituent elements and which facilitates later rendering. Expression trees typically comprise a plurality of nodes including leaf nodes, unary nodes and binary nodes. Nodes of higher degree, or of alternative definition may also be used. A leaf node, being the outer most node of an expression tree, has no descendent nodes and represents a primitive constituent of an image. Unary nodes represent an operation which modifies the pixel data coming out of the part of the tree below the unary operator. Unary nodes include such operations as colour conversions, convolutions (blurring etc) and operations such as red-eye removal. A binary node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. Binary nodes represent an operation which combines the pixel data of its two children to form a single result. For example, a binary node may be one of the standard “compositing operators” such as OVER. IN, OUT, ATOP aid alpha-XOR, examples of which and others are seen in FIG. 7.
Several of the above types of nodes may be combined to form a compositing tree 800, as shown in FIG. 8, representing an image where a representation of each portion of the image is retained at each of the nodes (e.g. 801) For the compositing tree 800, the result of the left-hand side of the tree 800 is retained at node 803, and may be interpreted as a colour converted image being clipped to spline boundaries. A path region represented by these spline boundaries is stored at the node 801 of the tree 800 and the resulting region representing the clipped image is stored at node 803. The clipped image region is composited with a second image which is stored at node 805.
Although the non-transparent area of a graphical element may of itself be of a certain size, it need not be entirely visible in a final image, or only a portion of the element may have an effect on the final image. For example, assume an image of a certain size is to be displayed on a display. If the image is positioned so that only the top left corner of the image is displayed by the display device, the remainder of the image is not displayed. The final image as displayed on the display device thus comprises the visible portion of the image, and the invisible portion in such a case need not be rendered.
Another way in which only a portion of an element may have an effect on a final image is when the portion is obscured by another element. For example, a final image to be displayed (or rendered) may comprise one or more opaque graphical elements, some of which obscure other graphical elements. Hence, the obscured elements have no effect on the final image.
Many conventional compositing models consider each node of a compositing tree to be conceptually infinite in extent. Therefore, to construct the final image, such a conventional system applies a compositing equation at every pixel of the output image. Interactive frame rates of the order greater than 15 frames per second can be achieved in such a system, since pixel operations are quite simple and can be highly optimised. These highly optimised pixel operations can be fast enough to produce acceptable frame rates without requiring complex code. However, this is certainly not always true in a compositing environment.
The per-pixel cost of compositing can be quite high since an image is typically rendered in 24-bit colour (e.g. Red, Green, Blue (RGB)) in addition to an 8-bit alpha channel, thus giving 32 bits per pixel. Each compositing operator has to deal with each of the four channels. Therefore, an approach of completely generating every pixel of every required frame when needed is highly inefficient.
The basic shape of operands to compositing operators in most current rendering systems is a rectangle or bounding box, regardless of the actual shape of the object being composited. Thus, it is a relatively simple operation to write an operator which composites within the intersection area of two bounding boxes. However, as a bounding box typically does not accurately represent the actual bounds of a graphical element, such an operation can result in a lot of unnecessary compositing of completely transparent pixels over completely transparent pixels. Furthermore, when the typical make-up of a composition is examined, it can be noticed that areas of many graphical elements are completely opaque. This opaqueness can be exploited during the compositing operation. However, these areas of complete opaqueness are usually non-rectangular and so are difficult to exploit using compositing arguments described by bounding boxes. If irregular regions are used for exploiting opaque objects when compositing, then these regions can then be combined in some way to determine where composting should occur. Furthermore, if any such region is known to be fully transparent or fully opaque, further optimisations are possible.
Most conventional rendering systems fail to exploit similarities in a composition of graphical elements between one frame and the next. Since it is rare for every graphical element of an image to change from frame to frame, large areas of a compositing tree typically remain unchanged. Thus, it is only necessary to render those components of an image that have been altered by a particular action. If incremental changes are made to a compositing tree, then only a reduced amount of updating is necessary to affect the change.
Many current graphical systems use what is known as an ‘immediate mode’ application program interface (API). This means that for each frame to be rendered, a complete corresponding set of rendering commands is sent to the API. However, sending the complete set of rendering commands is somewhat inefficient in a compositing environment since, as discussed above, large sections of the compositing tree typically remain unchanged from one frame to the next, but are completely re-rendered anyway in an immediate mode API. On the other hand, a ‘retained mode’ API provides a complete compositing tree on a per-frame basis. In this case, a user provides an initial compositing tree, and then modifies the tree for each frame in order to effect a change. Changes which can be made to the tree include geometrically transforming part or all of the tree, modifying the tree structure (unlinking and linking subtrees), and modifying attributes (eg: colour) of individual nodes. Note that such modifications may not necessarily mean that the tree structure, for example as seen in FIG. 8, will change where only the attributes of an individual node have been modified.
A retained mode rendering system uses the combination of a number of techniques and assumptions to provide high quality images and high frame rates. Firstly, a retained mode rendering system uses irregular regions to minimise per-pixel compositing. For example, if one graphical element is on top of another, then pixel compositing is only needed inside the area where the two elements intersect. Having the ability to use irregular regions gives the ability to narrow down areas of interest much more accurately. Secondly, if an opaque graphical element is composited with another element using the OVER operator, for example, then the opaque graphical element completely obscures what the element is composited onto (inside the opaque element's area). This is a very useful property since it means that no expensive pixel compositing is required to achieve the output pixel within the area of overlap since the pixel value is the same as that at the equivalent point on the opaque element. Opaque elements induce similar behaviour in most of the compositing operators described above. Thirdly, in a retained mode rendering system it is often necessary to repeatedly redraw the compositing tree as graphical elements of the tree are updated. Therefore, an assumption is made that in the transition from one frame to the next, only pan of the compositing tree will change. This particular property can be exploited by caching away expensive-to-generate information regarding a composition so that the cached information can be re-used in a subsequent redraw operation from one frame to the next. Examples of expensive-to-generate information are regions of interest (e.g. boundaries of areas of intersection between graphical elements etc); pixel data (i.e. representing expensive composites etc); and topological relationships between graphical elements.
Caching away expensive-to-generate information regarding a composition of graphical elements, in order that the information can be reused in subsequent redrawing operations, can greatly improve processing and thus redrawing speed. However, if too much memory is used for storing the information, the speed of redrawing can actually be decreased due to increased memory paging.
One known method for compositing graphical objects in a retained mode rendering system, uses image data compression and decompression techniques in order to reduce the amount of memory required for storing images and in particular expensive-to-generate information. However, conventional compression techniques, such as the Joint Photographics Expert Group (JPEG) standard, tend to be too slow and thus, the processing speed lost due to compressing and decompressing images can outweigh any advantage gained through performing such compression and decompression.
Accordingly, an improved compression method for use within a rendering system, and in particular a retained mode rendering system, is clearly needed.